type MergeSort struct {
    data []int
}

func (m *MergeSort) Sort(data []int) {
    m.data = append([]int(nil), data...)
    m.dfs(0, len(m.data)-1)
    copy(data, m.data)
}

func (m *MergeSort) dfs(start, end int) {
    if start == end {
        return
    }

    mid := (start + end) / 2
    m.dfs(start, mid)
    m.dfs(mid+1, end)
    m.merge(start, mid, end)
}

func (m *MergeSort) merge(start, mid, end int) {
    i, j := start, mid+1
    temp := make([]int, 0, end-start+1)
    for i <= mid && j <= end {
        if m.data[i] < m.data[j] {
            temp = append(temp, m.data[i])
            i++
        } else {
            temp = append(temp, m.data[j])
             j++
         }
     }
     for ; i <= mid; i++ {
         temp = append(temp, m.data[i])
     }
     for ; j <= end; j++ {
         temp = append(temp, m.data[j])
     }
     copy(m.data[start:], temp)
}